/*
 * @lc app=leetcode.cn id=215 lang=typescript
 *
 * [215] 数组中的第K个最大元素
 */

// @lc code=start
const swap = (arr: number[], i: number, j: number) => {
    [arr[i], arr[j]] = [arr[j], arr[i]]
}

const partition = (arr: number[], left: number, right: number) => {
    // 在区间内随机取值作为轴值
    const mid = arr[Math.floor(Math.random() * (right - left + 1)) + left]
    let l = left, r = right
    while (l < r) {
        while (arr[l] < mid) l++
        while (arr[r] > mid) r--
        if (l < r) swap(arr, l, r)
        // 防止死循环
        if (arr[l] === arr[r] && l !== r) l++
    }
    return l
}

const quick = (arr: number[], left: number, right: number, minK: number) => {
    let index: number
    if (left < right) {
        index = partition(arr, left, right)
        if (minK === index) {
            return arr[index]
        } else if (minK < index) {
            return quick(arr, left, index - 1, minK)
        } else {
            return quick(arr, index + 1, right, minK)
        }
    }
    return arr[left]
}

//  思想：快速选择算法
//  随机选取一个轴值，通过交换将比其小的放在左边，比其大的放在右边 => 分区
//  比较 len-k 与选取的轴值的 index 的大小，小则再对左边区间快速选择，大则右边 => 分治

//  复杂度：O(n) O(1)

function findKthLargest(nums: number[], k: number): number {
    return quick(nums, 0, nums.length - 1, nums.length - k)
};
// @lc code=end
console.log(findKthLargest([1, 2, 3, 4, 5, 6, 7, 8, 10], 2));


